package com.dyz.leetcode._10_slidingWindow;

public class _643_findMaxAverage {
    //前缀和
    public double findMaxAverage(int[] nums, int k) {
        int[] prefixSum = new int[nums.length+1];
        prefixSum[0] = 0;
        for (int i = 1; i <=nums.length ; i++) {
            prefixSum[i] = prefixSum[i-1]+nums[i-1];
         }

        int maxSum = Integer.MIN_VALUE;
        for(int i=0; i<nums.length-k+1; i++){
            int sum = prefixSum[i+k] - prefixSum[i];
            maxSum = Math.max(sum, maxSum);
        }
        return (double) maxSum/k;

    }
    //滑动窗口
    public double findMaxAverage1(int[] nums, int k) {
        int maxSum = Integer.MIN_VALUE;
        int left = 0;
        int right = 0;
        int windowSum = 0;
        while (right<nums.length){
            windowSum += nums[right];
            if(right-left+1==k){
                maxSum = Math.max(maxSum, windowSum);
                windowSum -= nums[left];
                left++;
            }
            right++;
        }
        return (double) maxSum/k;

    }
}
